
// 25.K个一组翻转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 分两个循环来解决, 其中外循环负责每一组k个节点的起始和结束位置
        // 内循环负责调转方向
        if(k == 1) return head;

        auto reverse_ = [](ListNode* prev_ , ListNode* start , ListNode* finish , ListNode* back_)
        {
            ListNode* prev = start , *cur = prev->next;
            while(cur != back_)
            {
                ListNode* next = cur->next;
                cur->next = prev;

                prev = cur;
                cur = next;
            }
            if(prev_) prev_->next = prev;
            start->next = back_;
        };

        int i = 0;
        ListNode* tn = head , *prev = nullptr , *ret;
        while(tn)
        {
            ListNode* start = tn , *finish = tn;
            for(i = 0 ;i < k && tn; i++) 
            {
                finish = tn;
                tn = tn ->next;
            }
            if(prev == nullptr) ret = finish;
            if(i != k) break;
            cout << start->val << finish->val << endl;
            reverse_(prev , start , finish , tn);
            prev = start;
        }
        return ret;
    }
};